package kcsj;

import java.io.IOException;
import java.io.InputStream;
import java.util.Arrays;
import java.util.Scanner;

public class CoinChanging {
    private final int n;//硬币种类数量
    private final int[] T;// 面值
    private final int[] Coins;// 硬币数量
    private final int target;// 目标值
    private final int[] dp;// dp[i]表示把目标值为i时，最少需要几枚硬币
    private int maxValue = 0;

    public CoinChanging(int index) {
        //读取数据并初始化属性
        InputStream fin = CoinChanging.class.getResourceAsStream("/data/CoinChanging/test/coins" + index + ".in");
        assert fin != null : "找不到测试数据!";
        Scanner scanner = new Scanner(fin);
        n = scanner.nextInt();
        T = new int[n];
        Coins = new int[n];
        for (int i = 0; i < n; i++) {
            T[i] = scanner.nextInt();
            Coins[i] = scanner.nextInt();
            maxValue += T[i] * Coins[i];
        }
        target = scanner.nextInt();

        dp = new int[target + 1];
        Arrays.fill(dp, target + 1);//初始化一个最大值.全用面直为1的硬币所用数量为target,所以最小的最大值为target+1.
        dp[0] = 0;//找零为0时不需要找
        scanner.close();
        try {
            fin.close();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    private int solve() {
        int result = -1;

        if (target <= maxValue) {// 目标金额大于总金额,result=-1.
            for (int i = 0; i < n; i++) {//i:第i种硬币.遍历每一种硬币
                for (int j = 1; j <= Coins[i]; j++) {//第j个硬币.每一种硬币有Coins[i]个,对第i种硬币进行遍历
                    for (int k = target; k >= T[i]; k--) {
                        //用dp[当前面额]的值和dp[替换掉当前面额]中较小的替换当前面值
                        dp[k] = Math.min(dp[k], dp[k - T[i]] + 1);//状态转移方程

                        System.out.printf("T[%d] = %d -> k: %2d ->", i, T[i], k);
                        for (int index = 0; index < dp.length; index++) {
                            System.out.printf("%3d", dp[index]);
                            if (index == k) {
                                System.out.print("*");
                            }
                        }
                        System.out.println();
                    }
                    System.out.println();
                }
                System.out.println();
            }
            result = dp[target] > target ? -1 : dp[target];//判断值是否有效
        }
        return result;
    }

    public int getResult() {
        return solve();
    }

    public static void main(String[] args) {
        System.out.println("信计1902张倚睿");
        for (int i = 0; i <= 6; i++) {
            System.out.println(new CoinChanging(i).getResult());
        }
    }
}
